#include <stdio.h>
#include <stdint.h>  // 用于uint64_t，支持最大18446744073709551615的斐波那契数

/**
 * 计算第n项斐波那契数（n≥1）
 * @param n: 斐波那契数列的项数（1-based索引）
 * @return: 第n项斐波那契数（uint64_t类型，避免溢出）
 */
uint64_t fibonacci(uint32_t n) {
    // 边界条件：第1项和第2项均为1
    if (n == 1 || n == 2) {
        return 1;
    }

    uint64_t f0 = 1;  // 存储第k-2项（初始为第1项）
    uint64_t f1 = 1;  // 存储第k-1项（初始为第2项）

    // 循环从第3项计算到第n项，共循环n-2次
    for (uint32_t i = 3; i <= n; i++) {
        uint64_t temp = f1;  // 临时保存当前f1（第k-1项）
        f1 = f0 + f1;        // 计算第k项 = 第k-2项 + 第k-1项
        f0 = temp;           // 更新f0为原来的f1（第k-1项）
    }

    return f1;
}

// 测试主函数
int main() {
    // 测试前10项斐波那契数（与Python修正后结果一致）
    uint32_t test_nums[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    uint32_t test_count = sizeof(test_nums) / sizeof(test_nums[0]);

    printf("斐波那契数列前10项：\n");
    for (uint32_t i = 0; i < test_count; i++) {
        uint32_t n = test_nums[i];
        uint64_t result = fibonacci(n);
        printf("第%d项：%llu\n", n, result);
    }

    // 额外测试大项数（如第50项，验证无溢出）
    uint32_t big_n = 50;
    uint64_t big_result = fibonacci(big_n);
    printf("\n第%d项斐波那契数：%llu\n", big_n, big_result);

    return 0;
}